package com.sfx.算法专题.排序.heapsort;

class Code_1_findKthLargest {
    public int findKthLargest(int[] nums, int k) {
        int [] arr = new int[k];
        for(int i =0;i<k;++i) {
            arr[i] = nums[i];
        }
        heapify(arr);
        //让每一个元素与堆顶元素进行比较,如果比堆顶大则替换
        for(int i = k;i<nums.length;++i) {
            if(nums[i] > arr[0]) {
                arr[0] = nums[i];
                shiftDown(arr,0,arr.length);
            }
        }
        return arr[0];
    }

    //从最后一个父节点开始向下调整 -- >调整为小根堆
    private void heapify(int[] arr) {
        for(int i =(arr.length-1)/2;i>=0;--i) {
            shiftDown(arr,i,arr.length);
        }
    }
    private void shiftDown(int[] arr,int parent,int len) {
        int child = 2 * parent + 1;
        while(child < len) {
            if(child + 1< len && arr[child] > arr[child+1]) {
                child++;
            }
            if(arr[parent] > arr[child]) {
                swap(arr,parent,child);
                parent = child;
                child = 2* parent + 1;
            }else {
                //已经是小根堆了
                break;
            }
        }
    }
    private void swap(int[] arr,int parent,int child) {
        int tmp = arr[parent];
        arr[parent] = arr[child];
        arr[child] = tmp;
    }
}